{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"color:#777777;background-color:#ffffff;font-size:12px;text-align:right;\">\n",
    "\tprepared by Abuzer Yakaryilmaz (QuSoft@Riga) | November 10, 2018\n",
    "</div>\n",
    "<table><tr><td><i> I have some macros here. If there is a problem with displaying mathematical formulas, please run me to load these macros.</i></td></td></table>\n",
    "$ \\newcommand{\\bra}[1]{\\langle #1|} $\n",
    "$ \\newcommand{\\ket}[1]{|#1\\rangle} $\n",
    "$ \\newcommand{\\braket}[2]{\\langle #1|#2\\rangle} $\n",
    "$ \\newcommand{\\inner}[2]{\\langle #1,#2\\rangle} $\n",
    "$ \\newcommand{\\biginner}[2]{\\left\\langle #1,#2\\right\\rangle} $\n",
    "$ \\newcommand{\\mymatrix}[2]{\\left( \\begin{array}{#1} #2\\end{array} \\right)} $\n",
    "$ \\newcommand{\\myvector}[1]{\\mymatrix{c}{#1}} $\n",
    "$ \\newcommand{\\myrvector}[1]{\\mymatrix{r}{#1}} $\n",
    "$ \\newcommand{\\mypar}[1]{\\left( #1 \\right)} $\n",
    "$ \\newcommand{\\mybigpar}[1]{ \\Big( #1 \\Big)} $\n",
    "$ \\newcommand{\\sqrttwo}{\\frac{1}{\\sqrt{2}}} $\n",
    "$ \\newcommand{\\dsqrttwo}{\\dfrac{1}{\\sqrt{2}}} $\n",
    "$ \\newcommand{\\onehalf}{\\frac{1}{2}} $\n",
    "$ \\newcommand{\\donehalf}{\\dfrac{1}{2}} $\n",
    "$ \\newcommand{\\hadamard}{ \\mymatrix{rr}{ \\sqrttwo & \\sqrttwo \\\\ \\sqrttwo & -\\sqrttwo }} $\n",
    "$ \\newcommand{\\vzero}{\\myvector{1\\\\0}} $\n",
    "$ \\newcommand{\\vone}{\\myvector{0\\\\1}} $\n",
    "$ \\newcommand{\\vhadamardzero}{\\myvector{ \\sqrttwo \\\\  \\sqrttwo } } $\n",
    "$ \\newcommand{\\vhadamardone}{ \\myrvector{ \\sqrttwo \\\\ -\\sqrttwo } } $\n",
    "$ \\newcommand{\\myarray}[2]{ \\begin{array}{#1}#2\\end{array}} $\n",
    "$ \\newcommand{\\X}{ \\mymatrix{cc}{0 & 1 \\\\ 1 & 0}  } $\n",
    "$ \\newcommand{\\Z}{ \\mymatrix{rr}{1 & 0 \\\\ 0 & -1}  } $\n",
    "$ \\newcommand{\\Htwo}{ \\mymatrix{rrrr}{ \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} \\\\ \\frac{1}{2} & -\\frac{1}{2} & \\frac{1}{2} & -\\frac{1}{2} \\\\ \\frac{1}{2} & \\frac{1}{2} & -\\frac{1}{2} & -\\frac{1}{2} \\\\ \\frac{1}{2} & -\\frac{1}{2} & -\\frac{1}{2} & \\frac{1}{2} } } $\n",
    "$ \\newcommand{\\CNOT}{ \\mymatrix{cccc}{1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0} } $\n",
    "$ \\newcommand{\\norm}[1]{ \\left\\lVert #1 \\right\\rVert } $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> <font color=\"blue\"> Solutions for </font>Grover's Search</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"task1\"></a>\n",
    "<h3> Task 1 </h3>\n",
    "\n",
    "Design a quantum circuit with 4 qubits.\n",
    "\n",
    "Apply Hadamard to each qubit.\n",
    "\n",
    "Execute your circuit 1600 times.\n",
    "\n",
    "You should observe each basis state around 100 times.\n",
    "\n",
    "Reexecute your circuit 16000 times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Solution </h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import all necessary objects and methods for quantum circuits\n",
    "from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "from qiskit.tools.visualization import matplotlib_circuit_drawer as drawer\n",
    "\n",
    "qreg = QuantumRegister(4) # quantum register with 4 qubits\n",
    "creg = ClassicalRegister(4) # classical register with 4 bits\n",
    "mycircuit = QuantumCircuit(qreg,creg) # quantum circuit with quantum and classical registers\n",
    "\n",
    "# apply h-gate (Hadamard) to each qubit\n",
    "for i in range(4):\n",
    "    mycircuit.h(qreg[i])\n",
    "\n",
    "# measure both qubits\n",
    "mycircuit.measure(qreg,creg)\n",
    "    \n",
    "# execute the circuit 1600 times, and print the outcomes\n",
    "job = execute(mycircuit,Aer.get_backend('qasm_simulator'),shots=1600)\n",
    "counts = job.result().get_counts(mycircuit)\n",
    "for outcome in counts:\n",
    "    reverse_outcome = ''\n",
    "    for i in outcome:\n",
    "        reverse_outcome = i + reverse_outcome\n",
    "    print(reverse_outcome,\"is observed\",counts[outcome],\"times\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"task2\"></a>\n",
    "<h3> Task 2: Emulating Grover's search </h3>\n",
    "\n",
    "For this task, you can use the methods given in notebook <a href=\"B80_Reflections.ipynb\" target=\"_blank\">B80_Reflections</a>.\n",
    "\n",
    "Set the value of $ k $ to 4. Then, the size of list is $ 2^k = 16 $.\n",
    "\n",
    "Pick the value of $ m $ as 3, the number of the marked elements.\n",
    "\n",
    "As described above, $ \\ket{u} = \\sqrt{\\frac{3}{16}} \\ket{u_{marked}} + \\sqrt{\\frac{13}{16}} \\ket{u_{unmarked}} $.\n",
    "\n",
    "Create a quantum circuit with single qubit.\n",
    "\n",
    "States $ \\ket{1} $ and $ \\ket{0} $ represents the quantum state $ \\ket{u_{marked}} $ and $ \\ket{u_{unmarked}}$, respectively.\n",
    "\n",
    "Then, $ \\ket{u} = \\sqrt{\\frac{13}{16}} \\ket{0} + \\sqrt{\\frac{3}{16}} \\ket{1} $.\n",
    "\n",
    "<b>Determine the angle $ \\theta $, the angle between $ \\ket{u} $ and $ \\ket{0} $.</b>\n",
    "\n",
    "<b>Iterate Grover's search algorithm once by using your quantum circuit.</b>\n",
    "\n",
    "For each reflection, use ry-gate (rotation).\n",
    "<ul>\n",
    "    <li> Define a list to store all quantum states (with their labels) that will be visited.</li>\n",
    "    <li> Implement the first reflection on your qubit </li>\n",
    "    <li> Read the current quantum state and store it on your list </li>\n",
    "    <li> Implement the second reflection on your qubit </li>\n",
    "    <li> Read the current quantum state and store it on your list\n",
    "    <li> Draw all visited quantum states with their labels </li>\n",
    "    <li> Execute your circuit 100 times </li>\n",
    "</ul>\n",
    "\n",
    "Is this single iteration enough to observe state $ \\ket{1} $ more than state $ \\ket{0} $? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Solution </h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> Find angle theta ($\\theta$)</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the angle theta\n",
    "\n",
    "u2 = [(13/16)**0.5,(3/16)**0.5]\n",
    "print(u2)\n",
    "\n",
    "from math import acos # acos is the inverse of function cosine\n",
    "from math import pi \n",
    "\n",
    "def angle_between_two_quantum_states(quantum_state1,quantum_state2):\n",
    "    inner_product = quantum_state1[0] * quantum_state2[0] + quantum_state1[1] * quantum_state2[1]\n",
    "    return acos(inner_product) \n",
    "\n",
    "# angle between |u> and |0> \n",
    "theta2 = angle_between_two_quantum_states(u2,[1,0])\n",
    "print(theta2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4>The previously used functions</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# COPY-PASTE the functions from the notebook \"B80_Reflections\"\n",
    "\n",
    "def amplitudes_of_a_quantum_state(quantum_circuit):\n",
    "    # import all necessary objects and methods for quantum circuits\n",
    "    from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "    \n",
    "     # the following code is used to get the quantum state of a quantum circuit\n",
    "    job = execute(quantum_circuit,Aer.get_backend('statevector_simulator'))\n",
    "    current_quantum_state=job.result().get_statevector(quantum_circuit) \n",
    "    \n",
    "    # now we read the real parts of the amplitudes\n",
    "    the_first_amplitude = current_quantum_state[0].real # amplitude of |0>\n",
    "    the_second_amplitude = current_quantum_state[1].real # amplitude of |1>\n",
    "    \n",
    "    return[the_first_amplitude,the_second_amplitude]\n",
    "# end of function\n",
    "\n",
    "def visualize_quantum_states(quantum_states):\n",
    "    # import the useful tool for drawing figures in pythpn\n",
    "    from matplotlib.pyplot import plot, show, figure, Circle, axis, gca, annotate, arrow, text\n",
    "    # import the constant pi\n",
    "    from math import pi\n",
    "    \n",
    "    figure(figsize=(6,6), dpi=80) # size of the figure\n",
    "    gca().add_patch( Circle((0,0),1,color='black',fill=False) ) # draw the circle\n",
    "    # auxiliary points\n",
    "    plot(-1.3,0)\n",
    "    plot(1.3,0)\n",
    "    plot(0,1.3)\n",
    "    plot(0,-1.3)\n",
    "    # axes\n",
    "    arrow(0,0,1.1,0,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,-1.1,0,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,0,-1.1,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,0,1.1,head_width=0.04, head_length=0.08)\n",
    "    \n",
    "    # draw all quantum states\n",
    "\n",
    "    for quantum_state in quantum_states:\n",
    "        # show the quantum state as an arrow on the diagram\n",
    "        state_name = quantum_state[0] # label of the quantum state \n",
    "        x_value = quantum_state[1] # amplitude of |0>\n",
    "        y_value = quantum_state[2] # amplitude of |1>\n",
    "        # draw the arrow\n",
    "        arrow(0,0,x_value,y_value,head_width=0.04, head_length=0.04,color='blue')\n",
    "\n",
    "         # the following code is used to write the name of quantum states\n",
    "        if x_value<0: text_x_value=x_value-0.1\n",
    "        else: text_x_value=x_value+0.05\n",
    "        if y_value<0: text_y_value=y_value-0.1\n",
    "        else: text_y_value=y_value+0.05       \n",
    "        text(text_x_value,text_y_value,state_name)\n",
    "\n",
    "    show() # show the diagram\n",
    "# end of function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> One iteration of Grover's search algorithm </h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import all necessary objects and methods for quantum circuits\n",
    "from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "from qiskit.tools.visualization import matplotlib_circuit_drawer as drawer\n",
    "\n",
    "\n",
    "all_visited_quantum_states2 =[]\n",
    "\n",
    "\n",
    "qreg2 = QuantumRegister(1) # quantum register with 1 qubit\n",
    "creg2 = ClassicalRegister(1) # classical register with 1 bit\n",
    "mycircuit2 = QuantumCircuit(qreg2,creg2) # quantum circuit with quantum and classical registers\n",
    "\n",
    "\n",
    "# set the qubit to |u>\n",
    "# rotate by theta2\n",
    "# do not forget to multiply it by 2\n",
    "mycircuit2.ry(2*theta2,qreg2[0])\n",
    "\n",
    "# read and store the current quantum state\n",
    "[x,y] = amplitudes_of_a_quantum_state(mycircuit2)\n",
    "all_visited_quantum_states2.append(['u',x,y])\n",
    "\n",
    "\n",
    "# this is (-2*theta2) in the first iteration\n",
    "rotation_angle_for_the_first_reflection2 = -2 * theta2\n",
    "# this is always (2*theta2) more than (-1*rotation_angle_for_the_first_reflection2)\n",
    "rotation_angle_for_the_second_reflection2 = (2*theta2) + (-1*rotation_angle_for_the_first_reflection2)\n",
    "\n",
    "# the first reflection: rotate by rotation_angle_for_the_first_reflection2\n",
    "mycircuit2.ry(2*rotation_angle_for_the_first_reflection2,qreg2[0])\n",
    "# read and store the current quantum state\n",
    "[x,y] = amplitudes_of_a_quantum_state(mycircuit2)\n",
    "all_visited_quantum_states2.append(['r',x,y]) # the label is r (reflected state)\n",
    "\n",
    "# the second reflection: rotate by rotation_angle_for_the_second_reflection2\n",
    "mycircuit2.ry(2*rotation_angle_for_the_second_reflection2,qreg2[0])\n",
    "# read and store the current quantum state\n",
    "[x,y] = amplitudes_of_a_quantum_state(mycircuit2)\n",
    "all_visited_quantum_states2.append(['n',x,y]) # the label is n (new state)\n",
    "    \n",
    "    \n",
    "visualize_quantum_states(all_visited_quantum_states2)\n",
    "    \n",
    "    \n",
    "# measure both qubits\n",
    "mycircuit2.measure(qreg2,creg2)\n",
    "    \n",
    "    \n",
    "# execute the circuit 100 times, and print the outcomes\n",
    "job = execute(mycircuit2,Aer.get_backend('qasm_simulator'),shots=100)\n",
    "counts2 = job.result().get_counts(mycircuit2)\n",
    "for outcome in counts2:\n",
    "    reverse_outcome = ''\n",
    "    for i in outcome:\n",
    "        reverse_outcome = i + reverse_outcome\n",
    "    print(reverse_outcome,\"is observed\",counts2[outcome],\"times\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(all_visited_quantum_states2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "<a id=\"task3\"></a>\n",
    "<h3> Taks 3 </h3>\n",
    "\n",
    "For this task, you can use the methods given in notebook <a href=\"B80_Reflections.ipynb\" target=\"_blank\"> B80_Reflections </a>.\n",
    "\n",
    "Set the value of $ k $ to 6. Then, the size of list is $ 2^k = 64 $.\n",
    "\n",
    "Pick the value of $ m $ as 1, the number of the marked elements.\n",
    "\n",
    "As described above, $ \\ket{u} = \\sqrt{\\frac{1}{64}} \\ket{u_{marked}} + \\sqrt{\\frac{63}{64}} \\ket{u_{unmarked}} $.\n",
    "\n",
    "Create a quantum circuit with single qubit.\n",
    "\n",
    "States $ \\ket{1} $ and $ \\ket{0} $ represents the quantum state $ \\ket{u_{marked}} $ and $ \\ket{u_{unmarked}}$, respectively.\n",
    "\n",
    "Then, $ \\ket{u} = \\sqrt{\\frac{63}{64}} \\ket{0} + \\sqrt{\\frac{1}{64}} \\ket{1} $.\n",
    "\n",
    "<b>Determine the angle $ \\theta $, the angle between $ \\ket{u} $ and $ \\ket{0} $.</b>\n",
    "\n",
    "<b>Iterate Grover's search algorithm <u>three times</u> by using your quantum circuit.</b>\n",
    "\n",
    "For each reflection, use ry-gate (rotation).\n",
    "<ul>\n",
    "    <li> Define a list to store all quantum states (with their labels) that will be visited.</li>\n",
    "    <li> Iterate 3 times:\n",
    "        <ul>\n",
    "            <li> Implement the first reflection on your qubit </li>\n",
    "            <li> Read the current quantum state and store it on your list </li>\n",
    "            <li> Implement the second reflection on your qubit </li>\n",
    "            <li> Read the current quantum state and store it on your list</li>\n",
    "        </ul> </li>\n",
    "    <li> Draw all visited quantum states with their labels </li>\n",
    "    <li> Execute your circuit 100 times </li>\n",
    "</ul>\n",
    "\n",
    "Is 3 iterations enough to observe state $ \\ket{1} $ more than state $ \\ket{0} $?\n",
    "\n",
    "Try 4, 5, 6, 7, 8, 9, and 10 iterations.\n",
    "\n",
    "What is the best iteration number?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Solution </h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> Find angle theta ($\\theta$)</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the angle theta\n",
    "\n",
    "u3 = [(63/64)**0.5,(1/64)**0.5]\n",
    "print(u3)\n",
    "\n",
    "from math import acos # acos is the inverse of function cosine\n",
    "from math import pi \n",
    "\n",
    "def angle_between_two_quantum_states(quantum_state1,quantum_state2):\n",
    "    inner_product = quantum_state1[0] * quantum_state2[0] + quantum_state1[1] * quantum_state2[1]\n",
    "    return acos(inner_product) \n",
    "\n",
    "# angle between |u> and |0> \n",
    "theta3 = angle_between_two_quantum_states(u3,[1,0])\n",
    "print(theta3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4>The previously used functions</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# COPY-PASTE the functions from the notebook \"B80_Reflections\"\n",
    "\n",
    "def amplitudes_of_a_quantum_state(quantum_circuit):\n",
    "    # import all necessary objects and methods for quantum circuits\n",
    "    from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "    \n",
    "     # the following code is used to get the quantum state of a quantum circuit\n",
    "    job = execute(quantum_circuit,Aer.get_backend('statevector_simulator'))\n",
    "    current_quantum_state=job.result().get_statevector(quantum_circuit) \n",
    "    \n",
    "    # now we read the real parts of the amplitudes\n",
    "    the_first_amplitude = current_quantum_state[0].real # amplitude of |0>\n",
    "    the_second_amplitude = current_quantum_state[1].real # amplitude of |1>\n",
    "    \n",
    "    return[the_first_amplitude,the_second_amplitude]\n",
    "# end of function\n",
    "\n",
    "def visualize_quantum_states(quantum_states):\n",
    "    # import the useful tool for drawing figures in pythpn\n",
    "    from matplotlib.pyplot import plot, show, figure, Circle, axis, gca, annotate, arrow, text\n",
    "    # import the constant pi\n",
    "    from math import pi\n",
    "    \n",
    "    figure(figsize=(6,6), dpi=80) # size of the figure\n",
    "    gca().add_patch( Circle((0,0),1,color='black',fill=False) ) # draw the circle\n",
    "    # auxiliary points\n",
    "    plot(-1.3,0)\n",
    "    plot(1.3,0)\n",
    "    plot(0,1.3)\n",
    "    plot(0,-1.3)\n",
    "    # axes\n",
    "    arrow(0,0,1.1,0,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,-1.1,0,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,0,-1.1,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,0,1.1,head_width=0.04, head_length=0.08)\n",
    "    \n",
    "    # draw all quantum states\n",
    "\n",
    "    for quantum_state in quantum_states:\n",
    "        # show the quantum state as an arrow on the diagram\n",
    "        state_name = quantum_state[0] # label of the quantum state \n",
    "        x_value = quantum_state[1] # amplitude of |0>\n",
    "        y_value = quantum_state[2] # amplitude of |1>\n",
    "        # draw the arrow\n",
    "        arrow(0,0,x_value,y_value,head_width=0.04, head_length=0.04,color='blue')\n",
    "\n",
    "         # the following code is used to write the name of quantum states\n",
    "        if x_value<0: text_x_value=x_value-0.1\n",
    "        else: text_x_value=x_value+0.05\n",
    "        if y_value<0: text_y_value=y_value-0.1\n",
    "        else: text_y_value=y_value+0.05       \n",
    "        text(text_x_value,text_y_value,state_name)\n",
    "\n",
    "    show() # show the diagram\n",
    "# end of function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> Five iterations of Grover's search algorithm </h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import all necessary objects and methods for quantum circuits\n",
    "from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "from qiskit.tools.visualization import matplotlib_circuit_drawer as drawer\n",
    "\n",
    "\n",
    "all_visited_quantum_states3 =[]\n",
    "\n",
    "\n",
    "qreg3 = QuantumRegister(1) # quantum register with 1 qubit\n",
    "creg3 = ClassicalRegister(1) # classical register with 1 bit\n",
    "mycircuit3 = QuantumCircuit(qreg3,creg3) # quantum circuit with quantum and classical registers\n",
    "\n",
    "# set the qubit to |u>\n",
    "# rotate by theta3\n",
    "# do not forget to multiply it by 2\n",
    "mycircuit3.ry(2*theta3,qreg3[0])\n",
    "\n",
    "# read and store the current quantum state\n",
    "[x,y] = amplitudes_of_a_quantum_state(mycircuit3)\n",
    "all_visited_quantum_states3.append(['u',x,y])\n",
    "\n",
    "# this is -2 * theta3 in the first iteration\n",
    "rotation_angle_for_the_first_reflection3 = -2 * theta3\n",
    "# this is always (2*theta3) more than (-1*rotation_angle_for_the_first_reflection3)\n",
    "rotation_angle_for_the_second_reflection3 = (2*theta3) + (-1*rotation_angle_for_the_first_reflection3)\n",
    "\n",
    "for i in range(3): # three iterations # later check 4, 5, 6, 7, 8, 9, and 10\n",
    "\n",
    "    # the first reflection: rotate by rotation_angle_for_the_first_reflection3\n",
    "    mycircuit3.ry(2*rotation_angle_for_the_first_reflection3,qreg3[0])\n",
    "    # read and store the current quantum state\n",
    "    [x,y] = amplitudes_of_a_quantum_state(mycircuit3)\n",
    "    all_visited_quantum_states3.append(['r'+str(i+1),x,y]) # the labels are r1, r2, ... (reflected states)\n",
    "\n",
    "    # the second reflection: rotate by rotation_angle_for_the_second_reflection3\n",
    "    mycircuit3.ry(2*rotation_angle_for_the_second_reflection3,qreg3[0])\n",
    "    # read and store the current quantum state\n",
    "    [x,y] = amplitudes_of_a_quantum_state(mycircuit3)\n",
    "    all_visited_quantum_states3.append(['n'+str(i+1),x,y]) # the labels are n1, n2, ... (new states)\n",
    "    \n",
    "    # this will be increased by (-4*theta2) after each iteration\n",
    "    rotation_angle_for_the_first_reflection3 = rotation_angle_for_the_first_reflection3 -4* theta3\n",
    "    # this is always (2*theta2) more than (-1*rotation_angle_for_the_first_reflection3)\n",
    "    rotation_angle_for_the_second_reflection3 = (2*theta3) + (-1*rotation_angle_for_the_first_reflection3)\n",
    "# end of iterations\n",
    "\n",
    "visualize_quantum_states(all_visited_quantum_states3)\n",
    "    \n",
    "# measure both qubits\n",
    "mycircuit3.measure(qreg3,creg3)\n",
    "    \n",
    "# execute the circuit 100 times, and print the outcomes\n",
    "job = execute(mycircuit3,Aer.get_backend('qasm_simulator'),shots=100)\n",
    "counts3 = job.result().get_counts(mycircuit3)\n",
    "for outcome in counts3:\n",
    "    reverse_outcome = ''\n",
    "    for i in outcome:\n",
    "        reverse_outcome = i + reverse_outcome\n",
    "    print(reverse_outcome,\"is observed\",counts3[outcome],\"times\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(all_visited_quantum_states3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "<a id=\"task4\"></a>\n",
    "<h3> Task 4 </h3>\n",
    "\n",
    "Repeat Task 3 for $ k = 8 $ and $ m = 1 $, but algorithmically find the best iteration number, say $B$. \n",
    "\n",
    "You may execute your circuit 1000 times to have more reliable results.\n",
    "<hr>\n",
    "<i> Hint:\n",
    "\n",
    "For each iteration number, you may check how many times the state $ \\ket{1} $ is observed. \n",
    "<br><br>\n",
    "This value should be at least 500.\n",
    "\n",
    "And, when this value starts to decrease, you may announce the previous iteration number as the best. \n",
    "</i>\n",
    "<hr>\n",
    "Our solution outputs $ B $ as 12 in every execution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Solution </h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> Find angle theta ($\\theta$)</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the angle theta\n",
    "# k=8, 2^k = 256\n",
    "\n",
    "u4 = [(255/256)**0.5,(1/256)**0.5]\n",
    "print(u4)\n",
    "\n",
    "from math import acos # acos is the inverse of function cosine\n",
    "from math import pi \n",
    "\n",
    "def angle_between_two_quantum_states(quantum_state1,quantum_state2):\n",
    "    inner_product = quantum_state1[0] * quantum_state2[0] + quantum_state1[1] * quantum_state2[1]\n",
    "    return acos(inner_product) \n",
    "\n",
    "# angle between |u> and |0> \n",
    "theta4 = angle_between_two_quantum_states(u4,[1,0])\n",
    "print(theta4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4>The previously used functions</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# COPY-PASTE the functions from the notebook \"B80_Reflections\"\n",
    "\n",
    "def amplitudes_of_a_quantum_state(quantum_circuit):\n",
    "    # import all necessary objects and methods for quantum circuits\n",
    "    from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "    \n",
    "     # the following code is used to get the quantum state of a quantum circuit\n",
    "    job = execute(quantum_circuit,Aer.get_backend('statevector_simulator'))\n",
    "    current_quantum_state=job.result().get_statevector(quantum_circuit) \n",
    "    \n",
    "    # now we read the real parts of the amplitudes\n",
    "    the_first_amplitude = current_quantum_state[0].real # amplitude of |0>\n",
    "    the_second_amplitude = current_quantum_state[1].real # amplitude of |1>\n",
    "    \n",
    "    return[the_first_amplitude,the_second_amplitude]\n",
    "# end of function\n",
    "\n",
    "def visualize_quantum_states(quantum_states):\n",
    "    # import the useful tool for drawing figures in pythpn\n",
    "    from matplotlib.pyplot import plot, show, figure, Circle, axis, gca, annotate, arrow, text\n",
    "    # import the constant pi\n",
    "    from math import pi\n",
    "    \n",
    "    figure(figsize=(6,6), dpi=80) # size of the figure\n",
    "    gca().add_patch( Circle((0,0),1,color='black',fill=False) ) # draw the circle\n",
    "    # auxiliary points\n",
    "    plot(-1.3,0)\n",
    "    plot(1.3,0)\n",
    "    plot(0,1.3)\n",
    "    plot(0,-1.3)\n",
    "    # axes\n",
    "    arrow(0,0,1.1,0,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,-1.1,0,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,0,-1.1,head_width=0.04, head_length=0.08)\n",
    "    arrow(0,0,0,1.1,head_width=0.04, head_length=0.08)\n",
    "    \n",
    "    # draw all quantum states\n",
    "\n",
    "    for quantum_state in quantum_states:\n",
    "        # show the quantum state as an arrow on the diagram\n",
    "        state_name = quantum_state[0] # label of the quantum state \n",
    "        x_value = quantum_state[1] # amplitude of |0>\n",
    "        y_value = quantum_state[2] # amplitude of |1>\n",
    "        # draw the arrow\n",
    "        arrow(0,0,x_value,y_value,head_width=0.04, head_length=0.04,color='blue')\n",
    "\n",
    "         # the following code is used to write the name of quantum states\n",
    "        if x_value<0: text_x_value=x_value-0.1\n",
    "        else: text_x_value=x_value+0.05\n",
    "        if y_value<0: text_y_value=y_value-0.1\n",
    "        else: text_y_value=y_value+0.05       \n",
    "        text(text_x_value,text_y_value,state_name)\n",
    "\n",
    "    show() # show the diagram\n",
    "# end of function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4> Five iterations of Grover's search algorithm </h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import all necessary objects and methods for quantum circuits\n",
    "from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer\n",
    "from qiskit.tools.visualization import matplotlib_circuit_drawer as drawer\n",
    "\n",
    "\n",
    "how_many_times_state_one_observed = 0\n",
    "\n",
    "decrease = False\n",
    "\n",
    "number_of_iteration = 1\n",
    "\n",
    "while decrease == False:\n",
    "\n",
    "    qreg4 = QuantumRegister(1) # quantum register with 1 qubit\n",
    "    creg4 = ClassicalRegister(1) # classical register with 1 bit\n",
    "    mycircuit4 = QuantumCircuit(qreg4,creg4) # quantum circuit with quantum and classical registers\n",
    "\n",
    "    # set the qubit to |u>\n",
    "    # rotate by theta4\n",
    "    # do not forget to multiply it by 2\n",
    "    mycircuit4.ry(2*theta4,qreg4[0])\n",
    "\n",
    "\n",
    "    # this is -2 * theta4 in the first iteration\n",
    "    rotation_angle_for_the_first_reflection4 = -2 * theta4\n",
    "    # this is always (2*theta4) more than (-1*rotation_angle_for_the_first_reflection4)\n",
    "    rotation_angle_for_the_second_reflection4 = (2*theta4) + (-1*rotation_angle_for_the_first_reflection4)\n",
    "\n",
    "    for i in range(number_of_iteration):\n",
    "        \n",
    "        # the first reflection: rotate by rotation_angle_for_the_first_reflection4\n",
    "        mycircuit4.ry(2*rotation_angle_for_the_first_reflection4,qreg4[0])\n",
    "\n",
    "        # the second reflection: rotate by rotation_angle_for_the_second_reflcetion4\n",
    "        mycircuit4.ry(2*rotation_angle_for_the_second_reflection4,qreg4[0])\n",
    "    \n",
    "        # this will be increased by (-4*theta4) after each iteration\n",
    "        rotation_angle_for_the_first_reflection4 = rotation_angle_for_the_first_reflection4 -4* theta4\n",
    "        # this is always (2*theta4) more than (-1*rotation_angle_for_the_first_reflection4)\n",
    "        rotation_angle_for_the_second_reflection4 = (2*theta4) + (-1*rotation_angle_for_the_first_reflection4)\n",
    "    # end of iterations\n",
    "\n",
    "    \n",
    "    # measure both qubits\n",
    "    mycircuit4.measure(qreg4,creg4)\n",
    "    \n",
    "    # execute the circuit 1000 times, and print the outcomes\n",
    "    job = execute(mycircuit4,Aer.get_backend('qasm_simulator'),shots=1000)\n",
    "    counts4 = job.result().get_counts(mycircuit4)\n",
    "    print(number_of_iteration,counts4) # print the outcomes\n",
    "    for outcome in counts4:\n",
    "        if outcome == '1': \n",
    "            # how_many_times_state_one_observed is more than 500 and has a less value than the previous one\n",
    "            # then it is time to STOP\n",
    "            if how_many_times_state_one_observed> 500 and how_many_times_state_one_observed > counts4[outcome]: \n",
    "                print(\"B is\",number_of_iteration-1)\n",
    "                decrease = True\n",
    "            else: # we should continue\n",
    "                how_many_times_state_one_observed = counts4[outcome] # update how_many_times_state_one_observed\n",
    "                number_of_iteration = number_of_iteration + 1 # increase number_of_iteration"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
